package JZ.LC897;

/**
 * @author corn
 * @create 2020-08-09-20:21
 */

import java.util.ArrayList;
import java.util.List;

/**
 * 897. 递增顺序查找树
 * 给你一个树，请你 按中序遍历 重新排列树，使树中最左边的结点现在是树的根，并且每个结点没有左子结点，只有一个右子结点。
 * 提示：
 *     给定树中的结点数介于 1 和 100 之间。
 *     每个结点都有一个从 0 到 1000 范围内的唯一整数值。
 */
public class Solution {
    public TreeNode increasingBST(TreeNode root) {
        List<Integer> vals = new ArrayList();
        inorder(root, vals);
        TreeNode ans = new TreeNode(0);
        TreeNode cur = ans;
        for (int val: vals) {
            cur.right = new TreeNode(val);
            cur = cur.right;
        }
        return ans.right;
    }
    //中序遍历将数的值存入ArrayList中
    public void inorder(TreeNode node, List<Integer> vals) {
        if (node == null) return;
        inorder(node.left, vals);
        vals.add(node.val);
        inorder(node.right, vals);
    }
}
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}